package zuo.test7_prefixTree;

/**
 * @Author: Forx
 * @Data: 2021/6/16
 * @Desc: Algorithm - zuo.test7_prefixTree
 * @Version: v1.0
 */

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *
 * 在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到
 * 一个答案的算法，叫作贪心算法。
 * 也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
 * 局部最优-?->整体最优
 *
 * */
public class MyGreedy {

    /**
     *
     *  一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。
     * 给你每一个项目开始的时间和结束的时间（给你一个数组，里面是一个个具体
     * 的项目）,你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。
     * 返回这个最多的宣讲场次。
     *
     * 要按照谁结束时间早来排序
     *
     * 不用证明,懵一个策略,然后用暴力解法通过大量的测试用例来验证对不对
     * */
    public static class Program{
        public int start;
        public int end;

        public Program(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static int bestArrange(Program[] programs,int startTime){
        Arrays.sort(programs, new Comparator<Program>() {
            @Override
            public int compare(Program o1, Program o2) {
                return o1.end-o2.end;
            }
        });
        int res = 0;
        for(Program program:programs){
            if(startTime <= program.start){
                res++;
                startTime = program.end;
            }
        }
        return res;
    }
    /**
     *
     * 一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金
     * 条，不管切成长度多大的两半，都要花费20个铜板。
     * 一群人想整分整块金条，怎么分最省铜板？
     * 例如，给定数组{10,20,30},代表一共三个人，整块金条长度为10+20+30=60。
     * 金条要分成10,20,30三个部分。如果先把长度60的金条分成10和50,花费60;
     * 再把长度50的金条分成20和30,花费50;一共花费110铜板。
     * 但是如果先把长度60的金条分成30和30,花费60;再把长度30金条分成10和20,
     * 花费30;一共花费90铜板。
     * 输入一个数组，返回分割的最小代价。
     *
     * 利用哈夫曼算法
     *
     * */

    public static int getMinConsume(int[] data){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for(Integer i:data){
            priorityQueue.add(i);
        }
        int res = 0;
        while (priorityQueue.size()>1){
            int numa =0;
            int numb =0;
            numa = priorityQueue.poll();
            numb = priorityQueue.poll();
            res+=numa+numb;
            priorityQueue.add(numa+numb);
        }
        return res;
    }

    /**
     *
     * 输入：
     * 正数数组costs
     * 正数数组profits
     * 正数k
     * 正数m
     * 含义：
     * costs[i]表示i号项目的花费
     * profits[i]表示i号项目在扣除花费之后还能挣到的钱（利润）
     * k表示你只能串行的最多做k个项目
     * m表示你初始的资金
     * 说明：
     * 你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
     * 输出：
     * 你最后获得的最大钱数。
     *
     * 哈夫曼 - 大根堆
     *
     * */

    public static class project{
        public int costs;
        public int profit;
    }

    public static int getMaxProfit(project[] projects,int k,int m){
        //花费从小到大排
        Arrays.sort(projects, new Comparator<project>() {
            @Override
            public int compare(project o1, project o2) {
                return o1.costs-o2.costs;
            }
        });
        //利润从小到大排
        Arrays.sort(projects, new Comparator<project>() {
            @Override
            public int compare(project o1, project o2) {
                return o1.profit-o2.profit;
            }
        });

        //越靠后虽然花费高,但利润也高

        int[] costs_profit = new int[projects.length];
        for (int i = 0; i < costs_profit.length; i++) {
            costs_profit[i] = projects[i].profit+projects[i].costs;
        }
        int have = m;
        int index = 0;
        while (k>0){
            for (int i = 0; i < projects.length; i++) {
                if(projects[i]!=null && have>projects[i].costs){
                    index = i;
                }
            }
            have+=costs_profit[index];
            projects[index] = null;
            k--;
        }
        return have;
    }
    /**
     *
     * 先将花费排入小根堆,然后排出能做的项目
     * 再将能做的项目排入大根堆,然后排出利润最大的
     *
     *
     * */
    public static int getMaxProfit_heap(project[] projects,int k,int m){
        PriorityQueue<project> lockedPro = new PriorityQueue<>(new Comparator<project>() {
            @Override
            public int compare(project o1, project o2) {
                return o1.costs-o2.costs;
            }
        });
        PriorityQueue<project> unlockPro = new PriorityQueue<>(new Comparator<project>() {
            @Override
            public int compare(project o1, project o2) {
                return o2.profit-o1.profit;
            }
        });
        for(project p: projects){
            lockedPro.add(p);
        }
        int have = m;
        while (k-->0 && (!unlockPro.isEmpty() || !lockedPro.isEmpty())){
            while (!lockedPro.isEmpty()){
                project p = lockedPro.poll();
                if(p.costs <= have){
                    unlockPro.add(p);
                }else {
                    break;
                }
            }
            project p = unlockPro.poll();
            have+=p.costs+p.profit;
        }
        return have;
    }

    /**
     *
     * 随时获得中位数
     *
     * 方法:维护两个堆,一个小根堆,一个大根堆
     * 如数据流为 5 3 7 4
     *  start 5->大
     *  3<5   3->大  abs 大.size-小.size>2 大->小  (大根堆的顶变成了3)
     *  7>3   7->小  abs 大.size-小.size<2
     *  4>3   4->小  abs 大.size-小.size>3 小->大  (小根堆的顶变成了5,大根堆的顶变成了4)
     *  ans = peek
     * */
    public static int getMid(int num){
        return 0;
    }
    /**
     *
     * N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列，
     * 也不在同一条斜线上。
     * 给定一个整数n,返回n皇后的摆法有多少种。
     * n=1,返回1。
     * n=2或3,2皇后和3皇后问题无论怎么摆都不行，返回0。
     * n=8,返回92。
     *
     *
     * */

    public static int NQueens(int n){



        return 0;
    }

    public static int NQueensProcess(int i,int[] record,int n){
        if(i==n){
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) {
            if(isValid(record,i,j)){
                record[i] = j;
                res+=NQueensProcess(i+1,record,n);
            }
        }
        return res;
    }


    /**
     * @param i 将要放入的行
     * @param j 将要放入的列
     * */
    public static boolean isValid(int[] record,int i,int j){
        for (int k = 0; k < i; k++) {
            if(j==record[k] || (Math.abs(record[k] - j) == Math.abs(i-k))){
                return false;
            }
        }
        return true;
    }

    public static int NQueen_Bit(int n){
        if(n<1 || n>32)return 0;
        int limit = n==32?-1:(1<<n)-1;//生成n位1 int limit = n==32?-1:(Integer.MIN_VALUE >> n) >>> (32 - n);
        return NQueensP_bit(limit,0,0,0);
    }

    public static int NQueensP_bit(int limit,int collim,int leftlim,int rightlim){
        if(collim==limit){
            return 1;
        }
        int pos = 0;
        int rightBit = 0;
        int res = 0;
        pos = limit & (~(collim | leftlim | rightlim));
        while (pos!=0){
            rightBit = pos &(~pos + 1);
            pos -= rightBit;
            res+=NQueensP_bit(limit,
                    (collim | rightBit),
                    (leftlim|rightBit)<<1,//每开新的一行限制都需要左右移位一次因为斜线是斜的
                    (rightlim | rightBit)>>>1
                    );

        }
        return res;
    }




    public static void main(String[] args) {
//        int[] buff1 = {10,10,20,20,30,40};
//        System.out.println(getMinConsume(buff1));

        for (int i = 1; i <= 32; i++) {
            System.out.println( Integer.toBinaryString ((Integer.MIN_VALUE >> i) >>> (32 - i)));
        }

    }





}
